
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;

// Definition for a Node.
class Node 
{
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) 
    {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) 
    {
        val = _val;
        children = _children;
    }
};

struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
    vector<vector<int>> levelOrder(Node* root)
    {
        if (nullptr == root)
            return {};

        queue<Node*> q;
        vector<int> level;
        vector<vector<int>> res;

        for (q.push(root); q.size();)
        {
            level.clear();

            for (int i = q.size(); i--;)
            {
                Node* front = q.front();
                q.pop();
                level.push_back(front->val);

                for (const auto& e : front->children)
                {
                    if (e)
                        q.push(e);
                }
            }

            res.push_back(level);
        }

        return res;
    }

    vector<int> rightSideView(TreeNode* root)
    {
        if (nullptr == root)
            return {};

        vector<int> res;
        queue<TreeNode*> q;

        for (q.push(root); q.size();)
        {
            res.push_back(q.back()->val);

            for (int i = q.size(); i--;)
            {
                TreeNode* front = q.front();
                q.pop();

                if (front->left)
                    q.push(front->left);
                if (front->right)
                    q.push(front->right);
            }
        }

        return res;
    }

    bool isValidBST1(TreeNode* root)
    {
        return _isValidBST1(root, LLONG_MIN, LLONG_MAX);
    }

    bool isValidBST2(TreeNode* root)
    {
        stack<TreeNode*> st;
        long long prev = LLONG_MIN;

        for (TreeNode* cur = root; st.size() || cur;)
        {
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            cur = st.top();
            st.pop();
            if (cur->val <= prev)
                return false;

            prev = cur->val;
            cur = cur->right;
        }

        return true;
    }

    int kthSmallest(TreeNode* root, int k)
    {
        int res = 0;
        stack<TreeNode*> st;

        for (TreeNode* cur = root; st.size() || cur;)
        {
            while (cur)
            {
                st.push(cur);
                cur = cur->left;
            }
            cur = st.top();
            st.pop();
            --k;
            if (0 == k)
            {
                res = cur->val;
                break;
            }

            cur = cur->right;
        }

        return res;
    }

    vector<string> binaryTreePaths(TreeNode* root)
    {
        string path;
        vector<string> res;

        _binaryTreePaths(root, path, res);

        return res;
    }

    vector<int> cur;
    vector<vector<int>> res;
    vector<vector<int>> permute1(vector<int>& nums)
    {
        vector<bool> vis(nums.size(), false);

        _permute1(nums, vis);

        return res;
    }

private:
    void _permute1(const vector<int>& nums, vector<bool>& vis)
    {
        if (cur.size() == nums.size())
        {
            res.push_back(cur);
            return;
        }

        for (int i = 0, n = nums.size(); i < n; ++i)
        {
            if (!vis[i])
            {
                cur.push_back(nums[i]);
                vis[i] = true;
                _permute1(nums, vis);
                vis[i] = false;
                cur.pop_back();
            }
        }
    }

    void _binaryTreePaths(TreeNode* root, string path, vector<string>& res)
    {
        if (!root)
            return;
        if (!root->left && !root->right)
        {
            res.push_back(path + to_string(root->val));
            return;
        }

        path += to_string(root->val) + "->";
        _binaryTreePaths(root->left, path, res);
        _binaryTreePaths(root->right, path, res);
    }

    bool _isValidBST1(TreeNode* root, long long low, long long up)
    {
        if (nullptr == root)
            return true;

        if (root->val <= low || root->val >= up)
            return false;

        return _isValidBST1(root->left, low, root->val) && _isValidBST1(root->right, root->val, up);
    }
};



int main()
{


	return 0;
}